public class MergeTwoLists {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {//21 合并有序链表
        ListNode head=new ListNode();
        ListNode temp=head;
        while(list1!=null&&list2!=null){
            if(list1.val<=list2.val){
                temp.next=list1;
                temp=temp.next;
                list1=list1.next;
            }else{
                temp.next=list2;
                temp=temp.next;
                list2=list2.next;
            }
        }
        if(list1==null){
            while(list2!=null){
                temp.next=list2;
                temp=temp.next;
                list2=list2.next;
            }
        }else{
            while(list1!=null)
            {
                temp.next=list1;
                temp=temp.next;
                list1=list1.next;
            }
        }
        return head.next;
    }
}
